package hashmap

import (
	"fmt"
)

type OpenAddrHashMap struct {
	// 这里使用动态数组来代替链表
	buckets     []*Pair
	size        int
	capacity    int
	extendRatio int
	loadTres    float64
	TOMBSTONE   *Pair
}

func NewHashMapOpenAddr(capacity int) *OpenAddrHashMap {
	return &OpenAddrHashMap{
		buckets:     make([]*Pair, capacity),
		size:        0,
		capacity:    capacity,
		extendRatio: 2,
		loadTres:    2. / 3.,
		TOMBSTONE: &Pair{
			key: -1,
			val: "-1",
		},
	}
}

func (a *OpenAddrHashMap) hash(k int) int {
	return (k % a.capacity)
}

func (a *OpenAddrHashMap) extend() {
	// save origin bucket
	originalBucket := make([]*Pair, a.capacity)
	copy(originalBucket, a.buckets)
	// calculate extend capacity
	a.capacity = a.capacity * a.extendRatio
	a.buckets = make([]*Pair, a.capacity)
	a.size = 0
	// use set() to migrate elements in the bucket so that the hash is recomputed and elements are placed in the correct position
	for _, v := range originalBucket {
		if v == nil || a.IsTombstone(v) {
			continue
		}
		a.Set(v.key, v.val)
	}
}

func (a *OpenAddrHashMap) loadFactor() float64 {
	return float64(a.size) / float64(a.capacity)
}

func (a *OpenAddrHashMap) Set(k int, v string) {
	if a.loadFactor() > a.loadTres {
		a.extend()
	}

	// k already exists, update the value
	index := a.findBucket(k)
	if a.buckets[index] == nil || a.IsTombstone(a.buckets[index]) {
		a.buckets[index] = &Pair{key: k, val: v}
		a.size++
	} else {
		a.buckets[index].val = v
	}
}

func (a *OpenAddrHashMap) findBucket(k int) int {
	hashVal := a.hash(k)
	firstTombstone := -1
	for a.buckets[hashVal] != nil {
		// found already exists key
		if a.buckets[hashVal].key == k {
			// the first tombstone value and the discovery value are exchanged to optimize the query efficiency
			if firstTombstone != -1 {
				a.buckets[firstTombstone] = a.buckets[hashVal]
				a.buckets[hashVal] = a.TOMBSTONE
				return firstTombstone
			}

			return hashVal
		}

		// the position is recorded when first tombstone value is found
		if a.IsTombstone(a.buckets[hashVal]) && firstTombstone == -1 {
			firstTombstone = hashVal
		}

		// linear probes,passing the tail and returning to the head
		hashVal = (hashVal + 1) % a.capacity
	}

	if firstTombstone != -1 {
		return firstTombstone
	}

	return hashVal
}

func (a *OpenAddrHashMap) Get(k int) string {
	index := a.findBucket(k)
	if a.buckets[index] == nil || a.IsTombstone(a.buckets[index]) {
		return ""
	}
	return a.buckets[index].val
}

func (a *OpenAddrHashMap) Delete(k int) {
	index := a.findBucket(k)
	if a.buckets[index] == nil || a.IsTombstone(a.buckets[index]) {
		return
	}
	a.buckets[index] = a.TOMBSTONE
	a.size--
}

func (a *OpenAddrHashMap) IsTombstone(val *Pair) bool {
	return val == a.TOMBSTONE
}

func (a *OpenAddrHashMap) Keys() []int {
	var res []int
	for _, v := range a.buckets {
		if v == nil || a.IsTombstone(v) {
			continue
		}

		res = append(res, v.key)
	}
	return res
}

func (a *OpenAddrHashMap) Print() {
	fmt.Printf("size: %v, capacity: %v ,loadThres: %v, extendRatio: %v \n", a.size, a.capacity, a.loadTres, a.extendRatio)
	for i, v := range a.buckets {
		if v == nil {
			continue
		}
		fmt.Printf("index:%v, %d => %v , is tombstone: %t \n", i, v.key, v.val, a.IsTombstone(v))

	}
}
